In [1]:
[1,3,5] + [ 3,4,1]
Out[1]:
In [2]:
range(10)
Out[2]:
In [3]:
l = [3,1,4]
In [4]:
[i^2 for i in range(11)]
Out[4]:
In [ ]:
In [5]:
def Bn(n):
if n == 0:
return [[]]
else:
return [[0]+u for u in Bn(n-1)] + [[1]+u for u in Bn(n-1)]
In [6]:
Bn(4)
Out[6]:
In [ ]:
Here I'm using Sagemath's Integer class who has a digit method. The argument padto complete with zero's. The returned list starts with the lowest significant bits.
In [7]:
Integer(11).digits(2, padto=15)
Out[7]:
In [8]:
def binary(n):
l = [None]*2^n
for i in range(2^n):
l[i] = Integer(i).digits(2, padto=n)
return l
In [9]:
binary(4)
Out[9]:
In [ ]:
In [ ]:
In [4]:
class binaryIter():
def __init__(self, n):
self._n = n
self._2n = 2^n
self._i = 0
def __iter__(self):
return self
def next(self):
if self._i == self._2n:
raise StopIteration
res = Integer(self._i).digits(2, padto=self._n)
self._i += 1
return res
In [5]:
it = iter(binaryIter(3))
In [6]:
it.next()
Out[6]:
In [7]:
list(binaryIter(3))
Out[7]:
In [5]:
it = binaryIter(100)
In [8]:
it.next()
Out[8]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [14]:
def binaryIterYield(n):
for i in range(2^n):
yield Integer(i).digits(2, padto=n)
In [15]:
it = iter(binaryIterYield(4))
In [16]:
it.next()
Out[16]:
In [ ]:
In [17]:
list(binaryIterYield(4))
Out[17]:
In [ ]:
In [18]:
class binaryIterGray(object):
def __init__(self, n):
self._n = n
self._g = [0]*n
self._t = range(n+1)
def __iter__(self):
return self
def next(self):
i = self._t[0]
if i == self._n:
raise StopIteration
self._g[i] = 1-self._g[i]
self._t[0] = 0
self._t[i] = self._t[i+1]
self._t[i+1] = i+1
def get(self):
return self._g
In [19]:
def listGrayBug(n):
it = binaryIterGray(n)
res = [it.get()]
for _ in it:
res.append(it.get())
return res
In [20]:
listGrayBug(3)
Out[20]:
In [ ]:
In [21]:
def listGray(n):
it = binaryIterGray(n)
res = [list(it.get())]
for _ in it:
res.append(list(it.get()))
return res
In [22]:
listGray(3)
Out[22]:
In [ ]:
In [23]:
class binaryIterGrayInst(object):
def __init__(self, n):
self._n = n
self._g = [0]*n
self._t = range(n+1)
self._c = 0
def __iter__(self):
return self
def next(self):
i = self._t[0]
print self._c.digits(2, padto=self._n)[::-1], self._t[::-1], i, self._g[::-1]
if i == self._n:
raise StopIteration
self._c += 1
self._g[i] = 1-self._g[i]
self._t[0] = 0
self._t[i] = self._t[i+1]
self._t[i+1] = i+1
def get(self):
return self._g
In [24]:
l = list(binaryIterGrayInst(4))
In [ ]:
In [10]:
def Bnk(n, k):
if k == 0:
return [[0]*n]
if k == n:
return [[1]*n]
else:
return [[0]+u for u in Bnk(n-1, k)] + [[1]+u for u in Bnk(n-1, k-1)]
In [17]:
l = Bnk(5,3)
l
Out[17]:
In [ ]:
In [12]:
def unrankBnk(n,k,i):
if i >= binomial(n,k):
raise ValueError
if n == 0:
return []
if i < binomial(n-1, k):
return [0]+unrankBnk(n-1, k, i)
else:
return [1]+unrankBnk(n-1, k-1, i-binomial(n-1, k))
In [16]:
unrankBnk(5, 5, 0)
Out[16]:
In [ ]:
In [ ]:
In [ ]:
In [28]:
def unrankBnk(n,k,i):
if i >= binomial(n,k):
raise ValueError
if k == 0:
return [0]*n
if k == n:
return [1]*n
if i < binomial(n-1, k):
return [0]+unrankBnk(n-1, k, i)
else:
return [1]+unrankBnk(n-1, k-1, i-binomial(n-1, k))
In [18]:
all(unrankBnk(5,3, i) == l[i] for i in range(len(l)))
Out[18]:
In [30]:
l[5]
Out[30]:
In [ ]:
In [31]:
binomial(100, 50), 2^64
Out[31]:
In [20]:
unrankBnk(100, 50, 100891344545564193334812197256)
Out[20]:
In [ ]:
In [32]:
def nextBin(l):
i = 0
while i < len(l) and l[i] == 1:
l[i] = 0
i += 1
if i == len(l):
raise ValueError
else:
l[i] = 1
In [33]:
l = [1,1,0,1,1]
In [34]:
nextBin(l)
In [35]:
l
Out[35]:
In [36]:
def listBin(n):
l = [0]*n
res = [list(l)]
try:
while True:
nextBin(l)
res.append(list(l))
except ValueError:
pass
return res
In [37]:
listBin(4)
Out[37]:
In [ ]:
In [38]:
binomial(4,2)
Out[38]:
In [39]:
[ factorial(2*N)/factorial(N)/factorial(N+1) for N in range(20) ]
Out[39]:
In [ ]: